package heap

type MinHeap struct {
	a     []int
	n     int // 容量
	count int // 堆指针
}

func NewMinHeap(capacity int) *MinHeap {
	return &MinHeap{
		a:     make([]int, capacity+1),
		n:     capacity,
		count: 0,
	}
}

func (heap *MinHeap) Insert(data int) {
	if heap.count == heap.n {
		return
	}
	heap.count++
	heap.a[heap.count] = data
	heap.makeMinHeap(heap.count)
}

func (heap *MinHeap) makeMinHeap(top int) {
	// 从下往上堆化
	i := top
	parent := i / 2 // 根节点在i==1的位置
	for parent > 0 && heap.a[parent] > heap.a[i] {
		heap.swap(parent, i)
		i = parent
		parent = i / 2
	}
}

func (heap *MinHeap) RemoveMin() {
	if heap.count == 0 {
		return
	}

	// 将最后一个位置的元素放到堆顶（相当于删除堆顶）
	heap.swap(1, heap.count)
	heap.count--
	// 从新堆化
	heap.heapifyUpToDown(heap.count)
}

func (heap *MinHeap) Min() interface{} {
	return heap.a[1]
}

func (heap *MinHeap) Sort() {
	k := heap.count
	for k >= 1 {
		heap.swap(1, k)
		heap.heapifyUpToDown(k - 1)
		k--
	}
}

// 从上往下堆化
func (heap *MinHeap) heapifyUpToDown(count int) {
	for i := 1; i <= count/2; {
		maxIndex := i
		// 如果当前节点小于左子节点
		if heap.a[i] > heap.a[i*2] {
			maxIndex = i * 2
		}
		// 如果当前节点的右子节点大于maxIndex 且i*2+1没有超过最后一个节点
		if i*2+1 <= count && heap.a[maxIndex] > heap.a[i*2+1] {
			maxIndex = i*2 + 1
		}

		if maxIndex == i {
			break
		}

		heap.swap(i, maxIndex)
		i = maxIndex
	}
}

func (heap *MinHeap) Top() int {
	return heap.a[1]
}

func (heap *MinHeap) swap(i, j int) {
	heap.a[i], heap.a[j] = heap.a[j], heap.a[i]
}
